package baseclass.i_GreedyStrategy;

import java.util.PriorityQueue;
import java.util.Queue;

/**
 *  有若干个项目，每个项目有花费和收益两个指标。若规定最多只能做K个项目，并且给定初始资金M，一次
 *  只能做一个项目。问如果才能收益最大？
 *  输入： 参数1，正数数组costs 参数2， 正数数组profits 参数3，正数k 参数4， 正数m
 *  costs[i]表示i号项目的花费
 *  profits[i]表示i号项目在扣除花费之后还能挣到的钱(利润)
 *  k表示最多做k个项目
 *  m表示你初始的资金
 *  说明： 你每做完一个项目，马上获得的收益，可以支持你去做下一个项目。
 *  输出： 你最后获得的最大钱数
 * @date 2020/3/1 12:12
 */
public class BestProfits {
    static class Project{
        int cost;
        int profit;
        public Project(int cost, int profit) {
            this.cost = cost;
            this.profit = profit;
        }
    }

    public static int getMax(int[]costs,int[]profits,int k,int W){
        if(costs == null || profits == null || costs.length != profits.length)
            return 0;
        //把花费放入小跟堆
        Queue<Project> minCostQ = new PriorityQueue<>((p1,p2) -> p1.cost - p2.cost);
        for (int i = 0; i < profits.length; i++) {
            minCostQ.add(new Project(costs[i],profits[i]));
        }
        //把能够做的项目(项目花费 < 当前资金)根据利润放入大根堆
        Queue<Project> maxProfitQ =
                new PriorityQueue<>((p1,p2) -> p2.profit -p1.profit);
        //做K个项目
        for (int i = 0; i < k; i++) {
            //把小跟堆中能做的项目放入大根堆
            while (!minCostQ.isEmpty() && minCostQ.peek().cost <= W){
                maxProfitQ.add(minCostQ.poll());
            }
            //如果能做就做，加上利润，然后弹出项目
            if (!maxProfitQ.isEmpty()){
                W += maxProfitQ.poll().profit;
            }else {
                //没有能解锁的项目了
                return W;
            }
        }
        return W;
    }
    public static void main(String[] args) {
        int W = 100;
        int []profits = {10,20,50};
        int []costs = {50,100,1000};
        int k = 3;
        System.out.println(getMax(costs,profits,k, W));
    }
}
